package two.prefixSum_difference;

/**
 * 航班预订统计
 * 差分代码模板
 */
public class CorpFlightBookings {
    //时间复杂度：O(m*2+n)  暴力：O(m*n)
    //思路：差分+前缀和
    //对于区间的操作，可以转化为两个关键点（事件）；事件的影响从l开始，从r+1处消失；累加影响得到答案。
    public int[] corpFlightBookings(int[][] bookings, int n) {
        int[] B = new int[n + 2];//差分数组（要开大一点）
        for(int[] booking : bookings){
            int first = booking[0];
            int last = booking[1];
            int seats = booking[2];
            B[first] += seats;
            B[last + 1] -= seats;
        }
        int[] A = new int[n + 2];//原数组
        for(int i = 1; i <= n; i++){
            A[i] = A[i - 1] + B[i];
        }
        int[] answer = new int[n];//结果
        for(int i = 1; i <= n; i++){
            answer[i - 1] = A[i];
        }

        return answer;
    }
}
